package jm.data.structure.stack;

/**
 * @Description 栈的实现
 * @date 2022/4/7 14:24
 */
public class Stack<E> {

    private E[] elements;

    private int size;

    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public Stack(int size) {
        size = Math.max(size, DEFAULT_CAPACITY);
        elements = (E[]) new Object[size];
    }

    public Stack(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 获取栈的长度
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 入栈
     * @param e
     */
    public void push(E e){
        if (size >= elements.length){
            ensureCapacity(size + 1);
        }
        elements[size++] = e;
    }

    /**
     * 出栈
     * @return
     * @throws IndexOutOfBoundsException
     */
    public E pop() throws IndexOutOfBoundsException {
        if (size < 1){
            throw new IndexOutOfBoundsException("Size:" + size);
        }
        return elements[--size];
    }

    /**
     * 查看栈顶元素
     * @return
     */
    public E top(){
        if (size < 1){
            throw new IndexOutOfBoundsException("Size:" + size);
        }
        return elements[size - 1];
    }

    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }
}

